#include "pch.h"
#include "DesktopRegion.h"

#include <assert.h>
#include <algorithm>
#include <utility>

DesktopRegion::RowSpan::RowSpan(int32_t left, int32_t right)
	: left(left), right(right) {}

DesktopRegion::Row::Row(const Row&) = default;
DesktopRegion::Row::Row(Row&&) = default;

DesktopRegion::Row::Row(int32_t top, int32_t bottom)
	: top(top), bottom(bottom) {}

DesktopRegion::Row::~Row() {}

DesktopRegion::DesktopRegion() {}

DesktopRegion::DesktopRegion(const DesktopRect& rect) {
	AddRect(rect);
}

DesktopRegion::DesktopRegion(const DesktopRect* rects, int count) {
	AddRects(rects, count);
}

DesktopRegion::DesktopRegion(const DesktopRegion& other) {
	*this = other;
}

DesktopRegion::~DesktopRegion() {
	Clear();
}

DesktopRegion& DesktopRegion::operator=(const DesktopRegion& other) {
	Clear();
	rows_ = other.rows_;
	for (Rows::iterator it = rows_.begin(); it != rows_.end(); ++it) {
		// Copy each row.
		Row* row = it->second;
		it->second = new Row(*row);
	}
	return *this;
}

bool DesktopRegion::Equals(const DesktopRegion& region) const {
	// Iterate over rows of the tow regions and compare each row.
	Rows::const_iterator it1 = rows_.begin();
	Rows::const_iterator it2 = region.rows_.begin();
	while (it1 != rows_.end()) {
		if (it2 == region.rows_.end() || it1->first != it2->first ||
			it1->second->top != it2->second->top ||
			it1->second->bottom != it2->second->bottom ||
			it1->second->spans != it2->second->spans) {
			return false;
		}
		++it1;
		++it2;
	}
	return it2 == region.rows_.end();
}

void DesktopRegion::Clear() {
	for (Rows::iterator row = rows_.begin(); row != rows_.end(); ++row) {
		delete row->second;
	}
	rows_.clear();
}

void DesktopRegion::SetRect(const DesktopRect& rect) {
	Clear();
	AddRect(rect);
}

void DesktopRegion::AddRect(const DesktopRect& rect) {
	if (rect.is_empty())
		return;

	// Top of the part of the |rect| that hasn't been inserted yet. Increased as
	// we iterate over the rows until it reaches |rect.bottom()|.
	int top = rect.top();

	// Iterate over all rows that may intersect with |rect| and add new rows when
	// necessary.
	Rows::iterator row = rows_.upper_bound(top);
	while (top < rect.bottom()) {
		if (row == rows_.end() || top < row->second->top) {
			// If |top| is above the top of the current |row| then add a new row above
			// the current one.
			int32_t bottom = rect.bottom();
			if (row != rows_.end() && row->second->top < bottom)
				bottom = row->second->top;
			row = rows_.insert(row, Rows::value_type(bottom, new Row(top, bottom)));
		}
		else if (top > row->second->top) {
			// If the |top| falls in the middle of the |row| then split |row| into
			// two, at |top|, and leave |row| referring to the lower of the two,
			// ready to insert a new span into.
			assert(top <= row->second->bottom);
			Rows::iterator new_row = rows_.insert(
				row, Rows::value_type(top, new Row(row->second->top, top)));
			row->second->top = top;
			new_row->second->spans = row->second->spans;
		}

		if (rect.bottom() < row->second->bottom) {
			// If the bottom of the |rect| falls in the middle of the |row| split
			// |row| into two, at |top|, and leave |row| referring to the upper of
			// the two, ready to insert a new span into.
			Rows::iterator new_row = rows_.insert(
				row, Rows::value_type(rect.bottom(), new Row(top, rect.bottom())));
			row->second->top = rect.bottom();
			new_row->second->spans = row->second->spans;
			row = new_row;
		}

		// Add a new span to the current row.
		AddSpanToRow(row->second, rect.left(), rect.right());
		top = row->second->bottom;

		MergeWithPrecedingRow(row);

		// Move to the next row.
		++row;
	}

	if (row != rows_.end())
		MergeWithPrecedingRow(row);
}

void DesktopRegion::AddRects(const DesktopRect* rects, int count) {
	for (int i = 0; i < count; ++i) {
		AddRect(rects[i]);
	}
}

void DesktopRegion::MergeWithPrecedingRow(Rows::iterator row) {
	assert(row != rows_.end());

	if (row != rows_.begin()) {
		Rows::iterator previous_row = row;
		previous_row--;

		// If |row| and |previous_row| are next to each other and contain the same
		// set of spans then they can be merged.
		if (previous_row->second->bottom == row->second->top &&
			previous_row->second->spans == row->second->spans) {
			row->second->top = previous_row->second->top;
			delete previous_row->second;
			rows_.erase(previous_row);
		}
	}
}

void DesktopRegion::AddRegion(const DesktopRegion& region) {
	// TODO(sergeyu): This function is not optimized - potentially it can iterate
	// over rows of the two regions similar to how it works in Intersect().
	for (Iterator it(region); !it.IsAtEnd(); it.Advance()) {
		AddRect(it.rect());
	}
}

void DesktopRegion::Intersect(const DesktopRegion& region1,
	const DesktopRegion& region2) {
	Clear();

	Rows::const_iterator it1 = region1.rows_.begin();
	Rows::const_iterator end1 = region1.rows_.end();
	Rows::const_iterator it2 = region2.rows_.begin();
	Rows::const_iterator end2 = region2.rows_.end();
	if (it1 == end1 || it2 == end2)
		return;

	while (it1 != end1 && it2 != end2) {
		// Arrange for |it1| to always be the top-most of the rows.
		if (it2->second->top < it1->second->top) {
			std::swap(it1, it2);
			std::swap(end1, end2);
		}

		// Skip |it1| if it doesn't intersect |it2| at all.
		if (it1->second->bottom <= it2->second->top) {
			++it1;
			continue;
		}

		// Top of the |it1| row is above the top of |it2|, so top of the
		// intersection is always the top of |it2|.
		int32_t top = it2->second->top;
		int32_t bottom = std::min(it1->second->bottom, it2->second->bottom);

		Rows::iterator new_row = rows_.insert(
			rows_.end(), Rows::value_type(bottom, new Row(top, bottom)));
		IntersectRows(it1->second->spans, it2->second->spans,
			&new_row->second->spans);
		if (new_row->second->spans.empty()) {
			delete new_row->second;
			rows_.erase(new_row);
		}
		else {
			MergeWithPrecedingRow(new_row);
		}

		// If |it1| was completely consumed, move to the next one.
		if (it1->second->bottom == bottom)
			++it1;
		// If |it2| was completely consumed, move to the next one.
		if (it2->second->bottom == bottom)
			++it2;
	}
}

// static
void DesktopRegion::IntersectRows(const RowSpanSet& set1,
	const RowSpanSet& set2,
	RowSpanSet* output) {
	RowSpanSet::const_iterator it1 = set1.begin();
	RowSpanSet::const_iterator end1 = set1.end();
	RowSpanSet::const_iterator it2 = set2.begin();
	RowSpanSet::const_iterator end2 = set2.end();
	assert(it1 != end1 && it2 != end2);

	do {
		// Arrange for |it1| to always be the left-most of the spans.
		if (it2->left < it1->left) {
			std::swap(it1, it2);
			std::swap(end1, end2);
		}

		// Skip |it1| if it doesn't intersect |it2| at all.
		if (it1->right <= it2->left) {
			++it1;
			continue;
		}

		int32_t left = it2->left;
		int32_t right = std::min(it1->right, it2->right);
		assert(left < right);

		output->push_back(RowSpan(left, right));

		// If |it1| was completely consumed, move to the next one.
		if (it1->right == right)
			++it1;
		// If |it2| was completely consumed, move to the next one.
		if (it2->right == right)
			++it2;
	} while (it1 != end1 && it2 != end2);
}

void DesktopRegion::IntersectWith(const DesktopRegion& region) {
	DesktopRegion old_region;
	Swap(&old_region);
	Intersect(old_region, region);
}

void DesktopRegion::IntersectWith(const DesktopRect& rect) {
	DesktopRegion region;
	region.AddRect(rect);
	IntersectWith(region);
}

void DesktopRegion::Subtract(const DesktopRegion& region) {
	if (region.rows_.empty())
		return;

	// |row_b| refers to the current row being subtracted.
	Rows::const_iterator row_b = region.rows_.begin();

	// Current vertical position at which subtraction is happening.
	int top = row_b->second->top;

	// |row_a| refers to the current row we are subtracting from. Skip all rows
	// above |top|.
	Rows::iterator row_a = rows_.upper_bound(top);

	// Step through rows of the both regions subtracting content of |row_b| from
	// |row_a|.
	while (row_a != rows_.end() && row_b != region.rows_.end()) {
		// Skip |row_a| if it doesn't intersect with the |row_b|.
		if (row_a->second->bottom <= top) {
			// Each output row is merged with previously-processed rows before further
			// rows are processed.
			MergeWithPrecedingRow(row_a);
			++row_a;
			continue;
		}

		if (top > row_a->second->top) {
			// If |top| falls in the middle of |row_a| then split |row_a| into two, at
			// |top|, and leave |row_a| referring to the lower of the two, ready to
			// subtract spans from.
			assert(top <= row_a->second->bottom);
			Rows::iterator new_row = rows_.insert(
				row_a, Rows::value_type(top, new Row(row_a->second->top, top)));
			row_a->second->top = top;
			new_row->second->spans = row_a->second->spans;
		}
		else if (top < row_a->second->top) {
			// If the |top| is above |row_a| then skip the range between |top| and
			// top of |row_a| because it's empty.
			top = row_a->second->top;
			if (top >= row_b->second->bottom) {
				++row_b;
				if (row_b != region.rows_.end())
					top = row_b->second->top;
				continue;
			}
		}

		if (row_b->second->bottom < row_a->second->bottom) {
			// If the bottom of |row_b| falls in the middle of the |row_a| split
			// |row_a| into two, at |top|, and leave |row_a| referring to the upper of
			// the two, ready to subtract spans from.
			int bottom = row_b->second->bottom;
			Rows::iterator new_row =
				rows_.insert(row_a, Rows::value_type(bottom, new Row(top, bottom)));
			row_a->second->top = bottom;
			new_row->second->spans = row_a->second->spans;
			row_a = new_row;
		}

		// At this point the vertical range covered by |row_a| lays within the
		// range covered by |row_b|. Subtract |row_b| spans from |row_a|.
		RowSpanSet new_spans;
		SubtractRows(row_a->second->spans, row_b->second->spans, &new_spans);
		new_spans.swap(row_a->second->spans);
		top = row_a->second->bottom;

		if (top >= row_b->second->bottom) {
			++row_b;
			if (row_b != region.rows_.end())
				top = row_b->second->top;
		}

		// Check if the row is empty after subtraction and delete it. Otherwise move
		// to the next one.
		if (row_a->second->spans.empty()) {
			Rows::iterator row_to_delete = row_a;
			++row_a;
			delete row_to_delete->second;
			rows_.erase(row_to_delete);
		}
		else {
			MergeWithPrecedingRow(row_a);
			++row_a;
		}
	}

	if (row_a != rows_.end())
		MergeWithPrecedingRow(row_a);
}

void DesktopRegion::Subtract(const DesktopRect& rect) {
	DesktopRegion region;
	region.AddRect(rect);
	Subtract(region);
}

void DesktopRegion::Translate(int32_t dx, int32_t dy) {
	Rows new_rows;

	for (Rows::iterator it = rows_.begin(); it != rows_.end(); ++it) {
		Row* row = it->second;

		row->top += dy;
		row->bottom += dy;

		if (dx != 0) {
			// Translate each span.
			for (RowSpanSet::iterator span = row->spans.begin();
				span != row->spans.end(); ++span) {
				span->left += dx;
				span->right += dx;
			}
		}

		if (dy != 0)
			new_rows.insert(new_rows.end(), Rows::value_type(row->bottom, row));
	}

	if (dy != 0)
		new_rows.swap(rows_);
}

void DesktopRegion::Swap(DesktopRegion* region) {
	rows_.swap(region->rows_);
}

// static
bool DesktopRegion::CompareSpanRight(const RowSpan& r, int32_t value) {
	return r.right < value;
}

// static
bool DesktopRegion::CompareSpanLeft(const RowSpan& r, int32_t value) {
	return r.left < value;
}

// static
void DesktopRegion::AddSpanToRow(Row* row, int left, int right) {
	// First check if the new span is located to the right of all existing spans.
	// This is an optimization to avoid binary search in the case when rectangles
	// are inserted sequentially from left to right.
	if (row->spans.empty() || left > row->spans.back().right) {
		row->spans.push_back(RowSpan(left, right));
		return;
	}

	// Find the first span that ends at or after |left|.
	RowSpanSet::iterator start = std::lower_bound(
		row->spans.begin(), row->spans.end(), left, CompareSpanRight);
	assert(start < row->spans.end());

	// Find the first span that starts after |right|.
	RowSpanSet::iterator end =
		std::lower_bound(start, row->spans.end(), right + 1, CompareSpanLeft);
	if (end == row->spans.begin()) {
		// There are no overlaps. Just insert the new span at the beginning.
		row->spans.insert(row->spans.begin(), RowSpan(left, right));
		return;
	}

	// Move end to the left, so that it points the last span that ends at or
	// before |right|.
	end--;

	// At this point [start, end] is the range of spans that intersect with the
	// new one.
	if (end < start) {
		// There are no overlaps. Just insert the new span at the correct position.
		row->spans.insert(start, RowSpan(left, right));
		return;
	}

	left = std::min(left, (int)start->left);
	right = std::max(right, end->right);

	// Replace range [start, end] with the new span.
	*start = RowSpan(left, right);
	++start;
	++end;
	if (start < end)
		row->spans.erase(start, end);
}

// static
bool DesktopRegion::IsSpanInRow(const Row& row, const RowSpan& span) {
	// Find the first span that starts at or after |span.left| and then check if
	// it's the same span.
	RowSpanSet::const_iterator it = std::lower_bound(
		row.spans.begin(), row.spans.end(), span.left, CompareSpanLeft);
	return it != row.spans.end() && *it == span;
}

// static
void DesktopRegion::SubtractRows(const RowSpanSet& set_a,
	const RowSpanSet& set_b,
	RowSpanSet* output) {
	assert(!set_a.empty() && !set_b.empty());

	RowSpanSet::const_iterator it_b = set_b.begin();

	// Iterate over all spans in |set_a| adding parts of it that do not intersect
	// with |set_b| to the |output|.
	for (RowSpanSet::const_iterator it_a = set_a.begin(); it_a != set_a.end();
		++it_a) {
		// If there is no intersection then append the current span and continue.
		if (it_b == set_b.end() || it_a->right < it_b->left) {
			output->push_back(*it_a);
			continue;
		}

		// Iterate over |set_b| spans that may intersect with |it_a|.
		int pos = it_a->left;
		while (it_b != set_b.end() && it_b->left < it_a->right) {
			if (it_b->left > pos)
				output->push_back(RowSpan(pos, it_b->left));
			if (it_b->right > pos) {
				pos = it_b->right;
				if (pos >= it_a->right)
					break;
			}
			++it_b;
		}
		if (pos < it_a->right)
			output->push_back(RowSpan(pos, it_a->right));
	}
}

DesktopRegion::Iterator::Iterator(const DesktopRegion& region)
	: region_(region),
	row_(region.rows_.begin()),
	previous_row_(region.rows_.end()) {
	if (!IsAtEnd()) {
		assert(row_->second->spans.size() > 0);
		row_span_ = row_->second->spans.begin();
		UpdateCurrentRect();
	}
}

DesktopRegion::Iterator::~Iterator() {}

bool DesktopRegion::Iterator::IsAtEnd() const {
	return row_ == region_.rows_.end();
}

void DesktopRegion::Iterator::Advance() {
	assert(!IsAtEnd());

	while (true) {
		++row_span_;
		if (row_span_ == row_->second->spans.end()) {
			previous_row_ = row_;
			++row_;
			if (row_ != region_.rows_.end()) {
				assert(row_->second->spans.size() > 0);
				row_span_ = row_->second->spans.begin();
			}
		}

		if (IsAtEnd())
			return;

		// If the same span exists on the previous row then skip it, as we've
		// already returned this span merged into the previous one, via
		// UpdateCurrentRect().
		if (previous_row_ != region_.rows_.end() &&
			previous_row_->second->bottom == row_->second->top &&
			IsSpanInRow(*previous_row_->second, *row_span_)) {
			continue;
		}

		break;
	}

	assert(!IsAtEnd());
	UpdateCurrentRect();
}

void DesktopRegion::Iterator::UpdateCurrentRect() {
	// Merge the current rectangle with the matching spans from later rows.
	int bottom;
	Rows::const_iterator bottom_row = row_;
	Rows::const_iterator previous;
	do {
		bottom = bottom_row->second->bottom;
		previous = bottom_row;
		++bottom_row;
	} while (bottom_row != region_.rows_.end() &&
		previous->second->bottom == bottom_row->second->top &&
		IsSpanInRow(*bottom_row->second, *row_span_));
	rect_ = DesktopRect::MakeLTRB(row_span_->left, row_->second->top,
		row_span_->right, bottom);
}
